package com.cn.codebrush.数组.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class No18四数之和 {
    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};  //8
        //-2808
        int[] nums1 = {-498,-492,-473,-455,-441,-412,-390,-378,-365,-359,-358,-326,-311,-305,-277,-265,-264,-256,-254,-240,-237,-234,-222,-211,-203,-201,-187,-172,-164,-134,-131,-91,-84,-55,-54,-52,-50,-27,-23,-4,0,4,20,39,45,53,53,55,60,82,88,89,89,98,101,111,134,136,209,214,220,221,224,254,281,288,289,301,304,308,318,321,342,348,354,360,383,388,410,423,442,455,457,471,488,488};
        int[] nums2 = {1,0,-1,0,-2,2};  //0

        int[] nums3 = {-2,-1,-1,1,1,2,2};      //0

        //System.out.println(fourSum2(nums,8));
        System.out.println(fourSum2(nums3,0));
        //System.out.println(fourSum(nums2,0));
    }


    /**
     * 双指针
     * AC
     */
    static List resList = new ArrayList();
    public static List<List<Integer>> fourSum2(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        for(int i=0;i<nums.length-1;i++){
            if(i>0 && nums[i-1] == nums[i]){continue;}
            for(int j=i+1;j<nums.length;j++){
                if(j>i+1 && nums[j-1] == nums[j]){continue;}
                int l = j+1;
                int r = len-1;
                while(l<r){
                    int sum = nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum == target){
                        resList.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        while(l<r && nums[l] == nums[l+1]){l++;}
                        while(l<r && nums[r-1] == nums[r]){r--;}
                        l++;
                        r--;
                    }else if(sum>target){
                        r--;
                    }else if(sum<target){
                        l++;
                    }
                }
            }
        }
        return resList;
    }




    /**
     * 回溯解法
     * 229 / 289 个通过测试用例  例：nums1
     */

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        fourSumHelper(nums,new ArrayList(),target,0);
        return resList;
    }

    public static void fourSumHelper(int[] nums,List list, int target,int q) {
        if(target == 0 && list.size() == 4){
            resList.add(new ArrayList<>(list));
            return ;
        }else if(list.size() > 4){
            return;
        }

        for(int i=q;i<nums.length;i++){
            if(i>q && nums[i-1] == nums[i]){continue;}
            list.add(nums[i]);
            fourSumHelper(nums,list,target-nums[i],i+1);
            list.remove(list.size()-1);
        }

    }
}
